1. Field of the Invention
The present invention relates generally to computer communications networks, and more particularly to regulating, monitoring and policing traffic on such computer communications networks.
2. Background Information
Enterprises, including businesses, governments and educational institutions, rely on computer networks to share and exchange information. A computer network typically comprises a plurality of entities interconnected by a communications media. An entity may consist of any device, such as a host or end station, that sources (i.e., transmits) and/or receives network messages over the communications media. A common type of computer network is a local area network (xe2x80x9cLANxe2x80x9d) which typically refers to a privately owned network within a single building or campus. A network device called a xe2x80x9cbridgexe2x80x9d is often used to implement xe2x80x9cbridgingxe2x80x9d function between entities connected to a LAN. Typically, the bridge is a computer that includes a plurality of ports, which are connected to different entities. The bridging function includes receiving data at a source port that originated from a sending entity, and transferring that data to at least one destination port for forwarding to a receiving entity.
In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc., to form a wide area network (xe2x80x9cWANxe2x80x9d) or subnet that may span an entire city, country or continent. One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. A router, for example, may be used to provide a xe2x80x9croutingxe2x80x9d function between two or more LANs. A multi-protocol router is often used to interconnect LANs executing different LAN standards. To perform these tasks, a router, which also is a computer having a plurality of ports, typically examines the destination address and source address of messages passing through the router. Routers typically operate at the network layer or layer-3 of the communications protocol stack utilized by the network, one such protocol is the Internet Protocol (IP) layer of the five layer Transmission Control Protocol/Internet Protocol (TCP/IP) Reference Model. Furthermore, if the LAN standards associated with the source entity and the destination entity are dissimilar (e.g., Ethernet and Token Ring), the router may also alter the format of the packet so that it may be received by the destination entity. Routers also execute one or more routing protocols or algorithms, which are used to determine the paths along which network messages are sent.
Congestion typically refers to the presence of too many packets in a subnet or a portion of a network, thereby degrading the network""s performance. Congestion occurs when the network devices are unable to keep up with an increase in traffic. The action of not forwarding a packet is called dropping a packet. Dropping packets often affects multiple upper layer applications simultaneously. Furthermore, many upper layer applications, such as TCP, re-send messages if no acknowledgments are received. The upper layer applications may require global synchronization because of packets being dropped, which may significantly exacerbate the congestion problem.
QoS is a feature that allows dropping of packets on a selective basis to avoid or reduce congestion in the network. Two components of QoS are xe2x80x9cclassificationxe2x80x9d and xe2x80x9cpolicing.xe2x80x9dPackets are classified into different traffic classes according to policy set by the network administrator. For each class, a policing algorithm is used to measure the incoming traffic and compare that measure with policing parameters set by the network-administrator. As a result of policing, depending on the current traffic-rate for this class of traffic, a packet may be found xe2x80x9cin profilexe2x80x9d or xe2x80x9cout of profilexe2x80x9d by the policing algorithm. An out of profile packet is dropped or marked. Marking increases the probability of the packets being dropped later by another device that applies QoS to the packet. A packet that is dropped or marked by the policing algorithm is referred to as a xe2x80x9cpolicedxe2x80x9d packet. An in profile packet is forwarded without marking and is referred to as a packet xe2x80x9cpermittedxe2x80x9d by the policing algorithm.
Various algorithms exist to perform policing. Each of these algorithms is implemented in a single logic-module called policer that performs the same computation for all packets belonging to a traffic class. Such a policer is referenced as a centralized policer, since the same module needs to perform the computation for all packets belonging to a traffic class. One such policing algorithm limits the total number bytes in all packets permitted in any arbitrary time-interval, T, to the value of (T* contract_rate+burst). Here and as defined below, xe2x80x9ccontract ratexe2x80x9d is a policing policy parameter meaning information per unit time, and xe2x80x9cburstxe2x80x9d is another policing policy parameter meaning the maximum information permitted in excess of the rate. This can be implemented in a policer called the token-bucket policer, which performs the following computation for every packet in a traffic class:xe2x80x94
where:xe2x80x94
current_time is a free-running counter that measures time,
packet_length is the number of bytes in the current packet and
last_update_time and bucket are states stored for each traffic class
A centralized policer requires all packets to be processed for policing in a single logic-module. So, packets that are processed in different logic modules cannot belong to the same traffic-class. An object of the present invention is to allow packets arriving at multiple logic-modules to be policed as a single traffic-class. Similarly, an associated object of the present invention is to allow packets arriving at multiple network devices to be policed as a single traffic class. The invention requires each such logic-module to send information about packets that the logic module processed to other such logic-modules. There is a cost associated with the communication capacity used for exchanging such information. If such xe2x80x9coverheadxe2x80x9d information is sent less often, it uses less of the capacity of the communication system, but it also decreases the accuracy of policing.
Token based policers are known in the art. One such method is disclosed in U.S. Pat. No. 5,831,971, filed Aug. 22, 1996 and issued Nov. 3, 1998, assigned to Lucent Technologies, Inc. This patent incorporates a token based xe2x80x9cleaky bucketxe2x80x9d algorithm with queuing algorithms arranged to comply with a given policing policy and to shape traffic incoming to a node into a compliant outgoing stream via some link. However, this patent does not disclose a policing of a class of traffic across an entire network.
It is an object of the present invention to provide different mechanisms to trigger export of information from a logic-module in order to provide flexibility of optimizing cost-accuracy tradeoff in policing traffic class or classes across a part or an entire network.
The present invention overcomes the limitations of the prior art by providing a system and method of employing multiple modules in one or more network devices to police a single traffic-class or multiple classes. And wherein such policing can be extended to operate across an entire network.
The inventive system and method implements the policing policy across the entire network, or part thereof, by providing many modules referenced as individual policers. Each individual policer can observe and police only a part of the traffic. In this system each individual policer uses xe2x80x9cglobal state variablesxe2x80x9d that stores the measure traffic for the entire traffic-class and xe2x80x9clocal state variablesxe2x80x9d that store the measure of the part of traffic that is permitted by this individual policer. Each individual policer exports the measure of traffic it permitted to all individual policers, in the form of the local state variables, or functions thereof. After exporting such information, the individual policer clears the local state variables. Upon receiving such exported information, all the individual policers update their global state variables. At any time, the global state variables of an individual policer account for the total of all the measure of traffic exported from all individual policers till that time. At any time, the local state variables of an individual policer account for the traffic that was permitted at the same individual policer since it last exported the measure of traffic it permitted.
The present invention provides individual policers that monitor and police part of the traffic. In order to accomplish this policing by individual policers the contract rate and the burst for an entire traffic class is provided to the individual policers. The individual policers measure their parts of the traffic and export that information to all the other individual policers. There is a mechanism for receiving, totalizing and storing the individual policer information exchanged from all the individual policers. That total is then compared to the contract rate and burst for the entire traffic class and a policing decision is made by each individual policer for its part of the traffic class. In an embodiment, there is a master policer that receives all the information from all the individual policers and applies the contract rate and the burst and makes policing decisions for the individual policers that is then sent back to the individual policers.
In other embodiment, the information can be accumulated and stored at the individual policers and where the individual policers store the own information and that of the other individual policers.
In other embodiment, there is a threshold established wherein the individual policer broadcasts its information to the other individual policers only when a threshold, previously set in accordance with the overall policing policy is determined for each individual policer, is exceeded. In another related embodiment, the individual policer exports its information containing only the new data received since the last such export in accordance with a time limit that is exceeded. A threshold also may be established wherein the individual policer exports its measure of its part of the traffic when the amount of data locally permitted exceeds a set local-rate threshold.
In yet other preferred embodiment, the individual policers export information applicable to multiple classes of traffic, and wherein the information is contained in one message. This information may be exported via the same medium used in the network, or alternatively the information may be sent via a medium separate from that used in the network.
In yet other embodiment, the present invention may be used together with token leaky bucket algorithms incorporating the above discussed elements to advantage.
In a preferred embodiment, the policing decision for each packet is made using a modified version of the token bucket algorithm, and including thresholds wherein the information messages between individual policers occurs only when these thresholds are exceeded. Such thresholds may be on the data received and/or time from last up date or combinations of both. Moreover, it is possible to interchange the information between the individual policers via channels or a medium outside that of the network itself. For example, dial up telephone/fax lines, and the like. However, the same principle may be employed to other centralized policing algorithms.
Various techniques are invented to trigger the export of information from the individual policers. This allows various means to reduce information exchanged between policers and increase the accuracy of policing. One technique may be superior to others in a given implementation in a given traffic condition.